/**
 * @file filename.cpp
 * @brief nullptr关键字用于标识空指针，与NULL不同，NULL为0
 * @author Monomania (1301519350@qq.com)
 * @version 0.1
 * @date 2021-09-23
 */
#include<iostream>
#include <vector> 
#include <string>
#include <list>
#include <map>
#include <algorithm> // std::minmax_element
#include <boost/algorithm/string.hpp>
#include <functional>
#include <iterator>
// #define NDEBUG
#include <assert.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE true
#define FALSE false
// 定义一个不可能的数
#define INF   -99999  
#define MAXSIZE 20 /* 存储空间初始分配量 */

typedef int Status; 
typedef int SElemType; /* SElemType类型根据实际情况而定，这里假设为int */

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};


class Solution {
public:
    bool isPalindrome(ListNode* head) {//O(n)、O(1)
        ListNode* slow = head, *fast = head,  *prev = nullptr;

        // 利用快慢指针寻找中点---中点为slow
        while (fast){//find mid node
            slow = slow->next;
            fast = fast->next ? fast->next->next: fast->next;
        }
        // 翻转链表后面的内容
        // slow = this->reverse(slow->next);
        while (slow){//reverse
            ListNode* temp = slow->next;
            slow->next = prev;
            prev = slow;
            slow = temp;
        }
        while (head && prev){//check
            if (head->val != prev->val){
                return false;
            }
            head = head->next;
            prev = prev->next;
        }
        return true;
    }
    // 还有问题
// private:
//     ListNode* reverse(ListNode* head){
//         // 递归到最后一个节点，返回新的新的头结点
//         if (head->next == nullptr) {
//             return head;
//         }
//         ListNode* newHead = reverse(head->next);
//         head->next->next = head;
//         head->next = nullptr;
//         return newHead;
//     }
};

void visit_list(ListNode* head){
    ListNode* tmp = head;
    while(tmp != nullptr){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << endl;
}


int main(int argc, const char** argv) {
    ListNode *L1 = new ListNode(1);
    L1->next = new ListNode(2);
    L1->next->next = new ListNode(2);
    L1->next->next->next = new ListNode(1);

    ListNode *L2 = new ListNode(1);
    L2->next = new ListNode(0);
    L2->next->next = new ListNode(1);
    visit_list(L2);

    Solution solu = Solution();
    cout << solu.isPalindrome(L2) << endl;


    return 0;
}
